home *** CD-ROM | disk | FTP | other *** search
/ Aminet 7 / Aminet 7 - August 1995.iso / Aminet / docs / misc / ConcNews.lha / news / general.programming / comp.programming_1589_000024.msg < prev    next >
Encoding:
Text File  |  1994-11-27  |  2.7 KB  |  76 lines
  1. Path: dd.chalmers.se!news.chalmers.se!sunic!EU.net!howland.reston.ans.net!cs.utexas.edu!swrinde!sgiblab!news.cs.indiana.edu!news.Arizona.EDU!math.arizona.edu!CS.Arizona.EDU!not-for-mail
  2. From: dave@CS.Arizona.EDU (Dave Schaumann)
  3. Newsgroups: comp.programming
  4. Subject: Re: Hash function for strings
  5. Date: 4 Mar 1994 17:04:23 -0700
  6. Organization: University of Arizona CS Department, Tucson AZ
  7. Lines: 64
  8. Message-ID: <2l8ia7$97d@caslon.CS.Arizona.EDU>
  9. References: <amundsj.1.0@novell.oih.no> <2l6kis$8jp@scax18.pki-nbg.philips.de>
  10. NNTP-Posting-Host: caslon.cs.arizona.edu
  11.  
  12. In article <2l6kis$8jp@scax18.pki-nbg.philips.de>,
  13. Frank Munkert <ln_fmu@sle20.pki-nbg.philips.de> wrote:
  14. |
  15. |In article <amundsj.1.0@novell.oih.no>, amundsj@novell.oih.no (AMUNDSEN JARLE/3AA/D) writes:
  16. |> I am trying to find a good hash function for strings, names that is, and
  17. |> wonder if anyone has an idea on how good such a function can hash. Given
  18. |> that the keys are not known in advance.
  19. |
  20. |The performance of several different hash function is discussed
  21. |in "Aho, Sethi, Ullman: Compilers - Principles, Techniques and Tools;
  22. |Addison-Wesley, Reading, 1986."
  23.  
  24. The hash function they use that performs the best is this (well,
  25. modified just a bit):
  26.  
  27.     int hash_pjw( char *s, unsigned int size ) {
  28.       char *p ; unsigned int h = 0, g ;
  29.  
  30.       for( p = s ; *p != '\0' ; p++ ) {
  31.         h = (h << 4) + *p
  32.         if( (g = h & 0xf0000000) ) { /* note: assumes 32-bit ints */
  33.           h = h ^ (g >> 24) ;        /* here, too */
  34.           h = h ^ g ;
  35.           }
  36.         }
  37.  
  38.       return h % size ;
  39.       }
  40.  
  41. I've used this with very good results for prime-sized hash tables and
  42. internal chaining.  For instance, here's the stats for loading /usr/dict/words
  43. into my hash table using hash_pjw:
  44.  
  45.     number of rehashes   : 9
  46.     population           : 24483
  47.     table size           : 55609
  48.     load factor          : 0.440270
  49.     total nodes searched : 73433
  50.     total search calls   : 52216
  51.     Avg nodes searched per call: 1.406331
  52.     probes  keys     %
  53.     ------  -----  ------
  54.         1   18982   77.53
  55.         2   3498    91.82
  56.         3   1218    96.79
  57.         4    449    98.63
  58.         5    182    99.37
  59.         6     83    99.71
  60.         7     36    99.86
  61.         8     15    99.92
  62.         9      7    99.95
  63.        10      6    99.97
  64.        11      5    99.99
  65.        12      1   100.00
  66.        15      1   100.00
  67.  
  68. Note that total search calls > population because of rehashing.
  69. The hash table starts out at a size of 101, which is probably too
  70. small, particularly if your planning on loading /usr/dict/words into
  71. the hash table very often :-).  I can also get a little better behavior
  72. by tweaking the probe function.
  73.  
  74. -- 
  75. Dave Schaumann        dave@cs.arizona.edu
  76.